package sword.offer;

/**
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动<br/>
 * 它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。<br/>
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。<br/>
 * 请问该机器人能够到达多少个格子？
 * 链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class Thirteen {
    /**
     * 初步思考后 使用DFS。<br/>
     * 虽然题目中，机器人可以向左、右、上、下移动，但是机器人的起点是在[0,0]<br/>
     * 所以对于每个元素来说，都是从其上边或者左边到达的。<br/>
     * 我们化解成子问题：<br/>
     * 在坐标为（0,0）的机器人的移动规则为 （0,1） （1,0）两个格子。<br/>
     * 依次内推，当机器人处于（0,1） （1,0）这两个位置的时候 又能到达多少个格子呢？<br/>
     *
     * 按照这样的思路我们发现，机器人是可以到达任意格子的，这一点很重要。也就是说我们完全可以遍历方块的所有格子<br/>
     * 但是别忘记了我们的限制条件。所以我们还需要写一个数位和的函数。<br/>
     * */
    class Solution {
        public int movingCount(int m, int n, int k) {
            boolean[][] visible = new boolean[m][n];
            return dfs(m,n,0,0,k,visible);
        }
        /**
         * 基线条件：
         * 1. 越界
         * 2. 不符合限制条件
         * 3. 已经访问过
         * */
        public int dfs(int m, int n, int i, int j,int k,boolean[][] visible){
            if(i-m >= 0 || j-n >= 0 || (calc(i)+calc(j) > k) || visible[i][j]){
                return 0;
            }
            visible[i][j] = true;
            return 1 + dfs(m, n, i+1, j, k, visible) + dfs(m, n, i, j+1, k, visible);
        }

        public int calc(int n){
            int res = 0;
            while(n != 0){
                res += n % 10;
                n /= 10;
            }
            return res;
        }
    }
}
